from collections import deque
from typing import List


class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        size = len(tasks)

        visited = {0: (1, 0)}

        # 当前时间段,当前时间,当前完成状态
        queue = deque([(1, 0, 0)])
        while queue:
            s0, t0, stat0 = queue.popleft()

            if visited[stat0] != (s0, t0):
                continue

            for i in range(size):
                if not stat0 & (1 << i):
                    stat1 = stat0 | (1 << i)
                    if t0 + tasks[i] <= sessionTime:
                        s1, t1 = s0, t0 + tasks[i]
                    else:
                        s1, t1 = s0 + 1, tasks[i]

                    if (stat1 not in visited
                            or s1 < visited[stat1][0]
                            or (s1 == visited[stat1][0] and t1 < visited[stat1][1])):
                        visited[stat1] = (s1, t1)
                        queue.append((s1, t1, stat1))

        final_stat = (1 << size) - 1
        return visited[final_stat][0]


if __name__ == "__main__":
    print(Solution().minSessions(tasks=[1, 2, 3], sessionTime=3))  # 2
    print(Solution().minSessions(tasks=[3, 1, 3, 1, 1], sessionTime=8))  # 2
    print(Solution().minSessions(tasks=[1, 2, 3, 4, 5], sessionTime=15))  # 1
